在正常导航的情况下，每个代价地图中的障碍物被视为一系列孤立的点，根据分辨率来说的话，越高就会导致障碍越多，并且可能在计算候选轨迹子集（取决于障碍物的数量）时引入更长的计算时间或不稳定性。另一方面，障碍物的转换也需要时间。但是，转换时间很大程度上取决于所选的算法，并且可以在单独的线程中执行。本章使用地图转换的方式对局部代价地图层的障碍物点进行处理，使得可行性检查步骤的距离计算的运算量大大减少。通过采用前景检测算法和匀速估计模型对代价地图的动态障碍物进行识别和位姿估计，使得时间弹性带算法能够具有动态避障的能力。
我们考虑在代价地图层引入地图转换，通过聚类算法将大量孤立的点转换为多边形，提高导航效率。聚类的本质是对对象进行分组，关联性强的对象分为同一类簇，相关性弱的对象分为不同类簇。聚类算法通常用于数据挖掘中的预处理步骤。
聚类的基本要求
（1）可伸缩性
不管对象数据集的大小，我们希望聚类算法都能对数据进行准确的划分
（2）处理不同数据类型的能力
虽然处理数值类型的应用场景占大多数，大部分聚类算法都针对处理数值类型来设计，但是在实际应用场景中也会出现需要处理其他类型数据（例如二元数据和序数型数据）的情况，如果不使用专门的聚类算法进行处理，在处理这些非数值类型数据的准确定性和快速性上会有折损
（3）发现任意形状类簇的能力
大部分聚类算法用欧式距离和曼哈顿距离来度量数据之间的相关性，如式（4.1）、（4.2）所示，假设x,y为n维空间中两点，则它们的欧式距离为
（4）领域最小化
对于某些情况下产生的数据集来说，让使用者确定参数是一件非常困难的事情，然而许多聚类算法的质量十分依赖输入的参数，在设计过程中，我们应当考虑减少让用户输入参数的情况。
（5）抗干扰性
在对数据集进行聚类时，孤立或者错误的数据会对结果产生一定程度的干扰，对噪声数据和错误数据的检测和排除能力也是衡量聚类算法性能的一项指标。
（6）次序不敏感性
一些聚类算法通过不断地加入新的数据来更新聚类结果，在这种情况下，以不同的先后顺序加入新数据，生成的聚类结果应该保持不变。
（7）高维性
许多聚类算法适用于处理二维或者三维数据，不过在高维空间中的数据分布的十分稀疏，所以处理能力可能比较弱。现实中许多数据可能包含若干维或者属性，聚类算法也要相应地能够处理这些数据。
（8）基于约束
在实际应用中，聚类算法不可能脱离现实生活的约束来进行聚类，同一个聚类算法在不同约束条件下产生的聚类结果也会不同。
（9）可解释性和可用性
我们希望聚类分析得到的聚类结果都能用特定的语义、知识进行解释并且能和实际的应用场景联系起来。
类效果比前一次更好，例如典型的K均值（K-means）聚类算法、K中心（K-mediods）聚类算法。
基于密度的聚类算法，使用密度函数进行聚类计算，只要检测到区域中点密度大于某一阈值就把它加到相应的类簇，例如DBSCAN聚类算法、CFSFDP聚类算法，它可以找出使用距离聚类方法找不出的不规则的聚类，并且无需手动设定分区数目。
将数据视为节点，用边来表示数据之间的关联性，将整个数据集构建为一个超图网络。去掉样本之间关联性弱于指定阈值的边，对每个样本点只保留k个关联性相对较强的边，得到K最近邻图，最后再在图上进行簇划分，例如最小生成树（MST）聚类、OPOSSUM聚类。
在使用DBSCAN聚类算法收集完代价地图中的聚类之后，我们考虑对聚类的点集进行处理，使之转化为基本几何单元。在不同的导航环境下我们可以选用不同算法进行聚类处理。
单调链算法
我们把包含离散点集的最小凸集称为凸包。凸包计算是最早的复杂几何算法之一，并且有很多变种。该算法还适用于外形与其顶点集合相同的多边形或一组线段。凸包的应用有很多：避免碰撞，确定隐藏对象和进行形状分析等。二维的凸包称为凸多边形，几何对象（例如点集或多边形）的凸包是包含该对象的最小凸集。我们定义凸集S为：集合S是凸集当且仅当任取P,QS，整个线段PQ也在集合S内。定义凸包P为：凸包是包含集合S的每个点的最小凸多边形，当且仅当对于P内的任意两个点A和B，线段AB都在P内时，P为凸包。
RANSAC算法是一种在一群样本中去掉噪声样本，获得有效样本的方式。一个基本的假设是，数据由局内点（即可以由某些模型参数集解释的数据点）和离群点（不适合模型的数据点）组成。离群点可能来自系统受到环境干扰后产生的噪声点，或者由于系统误差产生的对模型的错误测量。RANSAC假定，从数据集中任意选取一组局内点最后都能拟合出最符合数据集的模型参数。
RANSAC算法主要思想是通过以下两步反复迭代：（1）从输入数据集中随机选择包含最少数据项的样本子集（样本数量满足足够确定模型参数的最小数量），仅使用此样本子集来拟合模型并计算相应的模型参数。（2）算法将整个数据集的数据点与估计的模型进行匹配，如果某个点适用于估计的模型，认为它也是局内点，如果某个数据元素不在误差阈值之内，则将其视为离群点。
如果估计的模型能够包含足够多的局内点，则判定估计的模型足够合理。LinesDBSRANSAC采用了RANSAC算法，该插件将占据栅格转换为一组线（和点），转换分为两个阶段：
（1）使用DBSCAN算法确定聚类。
（2）使用RANSAC算法查找直线段模型，反复调用RANSAC以在每个聚类中找到多条线段，直到局内点的数量低于特定阈值为止。其余的离群点用作点，或者将其凸包的关键点用作点。
（3）输出是一个多边形容器（但每个多边形仅包含一个顶点（点）或两个顶点（线））
动态避障方案：导航框架通常假定导航环境为准静态环境，这种情况下既没有明确预测也没有考虑动态障碍物（例如人或其他机器人）的运动。代价地图层仅提供当前环境的静态地图，而没有提供占据栅格的时间演变信息，因此，规划器将移动障碍物估计的速度和方向信息用来规划路径。为了在动态环境中保证导航的鲁棒性，导航包加入了膨胀层，其中，静态占据栅格通过成倍降低代价衰减率而膨胀，在实际表现上，机器人规划了比实际更悲观的轨迹来规避障碍物。本文将基于代价地图中滑动窗口的前景检测算法引入导航框架，使得机器人在代价地图层能够实现动态障碍物的检测和跟踪。
该算法被集成到地图转换中，可以用于检测动态障碍物基于局部代价地图的瞬时变化，以基于代价地图层的变化而不是原始数据来识别动态障碍，可以将由于障碍物运动而产生的占据栅格和静态背景所有的占据栅格区分开来，并且补偿了机器人的自身运动产生的速度以获得障碍物速度的无偏估计。前向栅格被聚集成一组障碍物，针对这些障碍物，将基于模型的卡尔曼滤波器应用于障碍物运动的中进行状态估计。
导航节点根据采样到的动态障碍物的位置、形状、平移速度其不确定性信息，在每个采样间隔进行当前动态障碍位置的估计，局部路径规划器利用估计的障碍物运动提前规划无碰撞的机器人轨迹。为此，局部规划器的界面不仅应考虑当前的代价地图，还应考虑由于障碍物运动而引起的代价地图随时间的变化。
导航包与teb_local_planner一起使用的最常见选项是使用代价地图层信息。但是，代价地图层信息不包含任何时间信息，因此仅在每个采样间隔内提供环境的静态视图。跟踪障碍物并预测障碍物的运动（或简化为障碍物的当前速度）通常需要通过代价地图层信息的变化来进行，而不能用传感器原始的数据。因此，适当的机器人系统包括能够向规划器提供这种信息的单独的跟踪节点。
为了有效利用机器人模型和环境中障碍物的距离信息，我们引入气泡的概念，气泡代表机器人当前位姿下的自由空间的局部子集，使得程序能够在复杂且不断变化的环境中利用有关的自由空间信息，而无需计算整个自由空间。
前景检测算法通过减去两个移动平均滤波器的输出，得到带通滤波器，从而从局部代价地图层中提取动态障碍。二进制图将移动的前景对象的像元标记为true，将静态和无障碍区域的
像元标记为false。
由于气泡代表了围绕机器人位姿的局部无碰撞区域，我们在规划出的路径点周围生成气泡对自由空间进行检测，从而确定障碍物的质心和轮廓。然后把与单个障碍物相关或相连接的栅格进行聚类，之后跟踪这些栅格并估计它们的位置和速度，尽管这种方法在机器人移动时也可以使用，但理论背景是假设机器人处于观察状态，因此假定局部代价地图层的位置为相对于全局地图保持不变。
参考文献：
[1] 厉于行. 聚类分析中基于投影的κ均值算法 [D]; 浙江大学, 2012.
[2] 晏焕钱. 基于密度峰值聚类的两种改进算法的研究 [D]; 兰州大学, 2018.
[3] 林文珍, 黄惠. 三维点云中的二维标记检测 [J]. 集成技术, 2015, 4(03): 35-44.
[4] ALBERS F, RSMANN C, HOFFMANN F, et al. Online Trajectory Optimization and Navigation in Dynamic Environments in ROS [J]. 2019,
